package com.lw.leetcode.arr.b;

/**
 * Created with IntelliJ IDEA.
 * 1504. 统计全 1 子矩形
 *
 * @author liw
 * @version 1.0
 * @date 2022/4/2 15:31
 */
public class NumSubmat {

    public static void main(String[] args) {
        NumSubmat test = new NumSubmat();

        int[][] arr = {
                {1,0,1,1,1,1,1},
                {1,1,0,0,0,1,1},
                {1,1,1,0,0,1,1},
                {1,0,1,0,1,0,1},
                {1,0,1,1,1,0,1},
                {1,1,0,1,1,1,1},
                {1,0,0,1,1,0,1}};

        int i = test.numSubmat(arr);

        System.out.println(i);


    }

    public int numSubmat(int[][] mat) {
        int n = mat.length;
        int m = mat[0].length;
        int ans = 0;
        int[] arr = mat[0];
        for (int j = 0; j < m; ++j) {
            int col = arr[j];
            if (col == 0) {
                continue;
            }
            for (int k = j; k >= 0; --k) {
                if (arr[k] == 0) {
                    break;
                }
                ans++;
            }
        }

        for (int i = 1; i < n; ++i) {
            arr = mat[i];
            int[] last = mat[i - 1];
            for (int j = 0; j < m; ++j) {
                if (arr[j] == 0) {
                    continue;
                }
                arr[j] += last[j];
                int col = arr[j];
                for (int k = j; k >= 0; --k) {
                    if (arr[k] == 0) {
                        break;
                    }
                    col = Math.min(col, arr[k]);
                    ans += col;
                }
            }
        }
        return ans;
    }


}
